/**
 * Software License, Version 1.0
 * 
 * Copyright 2003 The Trustees of Indiana University.  All rights reserved.
 * 
 *
 *Redistribution and use in source and binary forms, with or without 
 *modification, are permitted provided that the following conditions are met:
 *
 *1) All redistributions of source code must retain the above copyright notice,
 * the list of authors in the original source code, this list of conditions and
 * the disclaimer listed in this license;
 *2) All redistributions in binary form must reproduce the above copyright 
 * notice, this list of conditions and the disclaimer listed in this license in
 * the documentation and/or other materials provided with the distribution;
 *3) Any documentation included with all redistributions must include the 
 * following acknowledgement:
 *
 *"This product includes software developed by the Community Grids Lab. For 
 * further information contact the Community Grids Lab at 
 * http://communitygrids.iu.edu/."
 *
 * Alternatively, this acknowledgement may appear in the software itself, and 
 * wherever such third-party acknowledgments normally appear.
 * 
 *4) The name Indiana University or Community Grids Lab or NaradaBrokering, 
 * shall not be used to endorse or promote products derived from this software 
 * without prior written permission from Indiana University.  For written 
 * permission, please contact the Advanced Research and Technology Institute 
 * ("ARTI") at 351 West 10th Street, Indianapolis, Indiana 46202.
 *5) Products derived from this software may not be called NaradaBrokering, 
 * nor may Indiana University or Community Grids Lab or NaradaBrokering appear
 * in their name, without prior written permission of ARTI.
 * 
 *
 * Indiana University provides no reassurances that the source code provided 
 * does not infringe the patent or any other intellectual property rights of 
 * any other entity.  Indiana University disclaims any liability to any 
 * recipient for claims brought by any other entity based on infringement of 
 * intellectual property rights or otherwise.  
 *
 *LICENSEE UNDERSTANDS THAT SOFTWARE IS PROVIDED "AS IS" FOR WHICH NO 
 *WARRANTIES AS TO CAPABILITIES OR ACCURACY ARE MADE. INDIANA UNIVERSITY GIVES
 *NO WARRANTIES AND MAKES NO REPRESENTATION THAT SOFTWARE IS FREE OF 
 *INFRINGEMENT OF THIRD PARTY PATENT, COPYRIGHT, OR OTHER PROPRIETARY RIGHTS. 
 *INDIANA UNIVERSITY MAKES NO WARRANTIES THAT SOFTWARE IS FREE FROM "BUGS", 
 *"VIRUSES", "TROJAN HORSES", "TRAP DOORS", "WORMS", OR OTHER HARMFUL CODE.  
 *LICENSEE ASSUMES THE ENTIRE RISK AS TO THE PERFORMANCE OF SOFTWARE AND/OR 
 *ASSOCIATED MATERIALS, AND TO THE PERFORMANCE AND VALIDITY OF INFORMATION 
 *GENERATED USING SOFTWARE.
 */
package cgl.narada.util;
 
/**
 * ShellSorter - Adapted from Data Structures and Algorithms - Waite Groupe
 * @author Shrideep Pallickara
 * $Revision$
 * $Date$
 */
public class ShellSorter {
  private int[] theArray;
  private int nElems;

  /** ShellSorter constructor. */
  public ShellSorter() {
    super();
  }

  /* Constructor specifying the number of data items */
  public ShellSorter(int max){
    theArray = new int[max]; // create the array
    nElems = 0; // no items yet
  }
  
  public void display() {
    System.out.print("A=");
    for (int j = 0; j < nElems; j++)
      // for each element,
      System.out.print(theArray[j] + " "); // display it
    System.out.println("");
  }
  /**
   * Code to perform when this object is garbage collected.
   * 
   * Any exception thrown by a finalize method causes the finalization to
   * halt. But otherwise, it is ignored.
   */
  protected void finalize() throws Throwable {
    super.finalize();
  }
  public void insert(int value) {
    theArray[nElems] = value; // insert it
    nElems++; // increment size
  }
 
  public int[] shellSort() {
    int inner, outer;
    int temp;
    int h = 1; // find initial value of h
    while (h <= nElems / 3)
      h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)
    
    while (h > 0) {
      /* decreasing h, until h=1,  h-sort the file */
      for (outer = h; outer < nElems; outer++) {
	temp = theArray[outer];
	inner = outer;
	/* one subpass (eg 0, 4, 8)*/
	while (inner > h - 1 && theArray[inner - h] >= temp) {
	  theArray[inner] = theArray[inner - h];
	  inner -= h;
	}
	theArray[inner] = temp;
      }
      h = (h - 1) / 3;
    }
    return theArray;
  } 

  /**
   * Starts the application.
   * @param args an array of command-line arguments
   */
  public static void main(java.lang.String[] args) {
    java.util.Hashtable h = new java.util.Hashtable();
    for (int i = 98; i < 107; i++) {
      h.put(new Integer(i), "Put in " + i);
    }
    h.put(new Integer(97), "Put in " + 97);
    h.put(new Integer(107), "Put in " + 107);
    ShellSorter sorter = new ShellSorter(h.size());
    for (java.util.Enumeration e = h.keys(); e.hasMoreElements();)
      sorter.insert(((Integer) e.nextElement()).intValue());
    int[] sortedKeys = sorter.shellSort();
    for (int i = 0; i < sortedKeys.length; i++) {
      System.out.println(sortedKeys[i]);
    }
  }
}
